import org.junit.jupiter.api.Test;

public class _29_两数相除_指数加倍 {
    @Test
    public void test(){
        System.out.println(divide(-2147483648, 1));
    }

    /**
     * 上一次使用暴力解法：每次减去除数，直到被除数小于除数
     * 注意-2147483648转为整数会超过int的范围，因为有一个0，所以int最大值是2^31-1
     * 这一次使用指数加倍的方法来减少循环的次数
     * @param dividend
     * @param divisor
     * @return
     */
    public int divide(int dividend, int divisor) {
        //先确定符号
        int sign=-1;
        if(dividend<0&divisor<0) sign=1;
        if (dividend>0&divisor>0) sign=1;
        long res=0;
        long dividend_long =Math.abs((long) dividend);
        long divisor_long=Math.abs((long) divisor);
        int i=1;
        int j=1;
        long temp=divisor_long;
        //先进行指数遍历，每次都翻倍
        while (dividend_long>=temp){
            res+=i;
            dividend_long-=temp;
            i=i<<1;
            temp=temp<<1;
        }
        //当dividend_long<temp的时候在进行一次一次遍历
        while (dividend_long>=divisor_long){
            res+=j;
            dividend_long-=divisor_long;
        }
        res=res*sign;
        if (res>Integer.MAX_VALUE||res<Integer.MIN_VALUE) return Integer.MAX_VALUE*sign;
        return (int)res;
    }
}
